맨위로가기

동적 계획법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

동적 계획법은 주어진 문제를 여러 하위 문제로 나누어 풀고, 그 해결책을 저장하여 재사용함으로써 계산 횟수를 줄이는 알고리즘 설계 기법이다. 최적화 문제, 최단 경로 문제, 행렬 곱셈 순서 문제 등에 활용되며, 그리디 알고리즘보다 정확한 결과를 얻을 수 있다. 하향식(Top-Down)과 상향식(Bottom-Up) 두 가지 구현 방식이 있으며, 최적 부분 구조와 부분 문제 중복성을 만족하는 문제에 적용된다. 1940년대 리처드 벨만이 처음 사용했으며, 컴퓨터 과학, 생물 정보학, 제어 이론, 경제학 등 다양한 분야에서 활용된다.

더 읽어볼만한 페이지

  • 동적 계획법 - 배낭 문제
    배낭 문제는 주어진 배낭 용량 내에서 물건들의 가치 합을 최대화하는 조합 최적화 문제로, 물건을 쪼갤 수 있는지, 개수 제한이 있는지에 따라 다양한 변형이 있으며, 동적 계획법, 탐욕 알고리즘 등으로 해결하고, NP-완전 문제에 속하며 자원 할당 문제 등에 응용된다.
  • 동적 계획법 - 차원의 저주
    차원의 저주는 고차원 공간에서 데이터 분석 및 모델링의 어려움을 나타내는 현상으로, 계산 시간 증가, 수치 오차 발생, 조합 폭발 등의 문제점을 야기한다.
  • 최적화 알고리즘 - 기댓값 최대화 알고리즘
  • 최적화 알고리즘 - 유전 알고리즘
    유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
동적 계획법
개요
유형최적화 방법
분야컴퓨터 과학, 수학, 경제학
문제 유형최적화 문제
전략문제를 더 작고 겹치는 하위 문제로 분할
속성겹치는 하위 문제
최적 하위 구조
상세 내용
기원리처드 벨먼, 1950년대
관련 개념메모이제이션
분할 정복
탐욕 알고리즘
휴리스틱

2. 설명

주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다. 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다.

때로는 단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다. 그러나 대다수의 문제는 이보다 훨씬 더 복잡한 프로그래밍을 요구한다. 그 중에 일부는 여러 개의 매개 변수를 이용하여 재귀 함수를 작성해야 하는 것도 있고, 아예 이러한 방법으로 동적 알고리즘을 짤 수 없는 문제 또한 존재한다.

"동적 계획법(dynamic programming)"이라는 말은 1940년대 리처드 E. 벨만이 처음 사용했으며, 1953년에 현재의 정의가 되었다.[21] 효율적인 알고리즘 설계 기법으로 알려진 대표적인 구조 중 하나이다. 대상 문제를 귀납적으로 풀 때 반복적으로 나타나는 작은 문제 사례에 대해 해답을 표에 기록하고 표를 채워가는 방식으로 계산을 진행하여, 불필요한 계산을 줄이는 알고리즘을 말한다. 특정 알고리즘을 지칭하는 것이 아니라, 위와 같은 기법을 사용하는 알고리즘의 총칭이다. 일반적으로 귀납적인 정의에 따라 재귀법으로 알고리즘을 만들면 계산 결과를 재사용하지 않지만, 입력이 단순한 구조로 해답이 같음을 확인하기 쉬울 때, 동일한 입력에 대해 계산이 완료되었는지 확인하고 결과를 재사용하여 메모리 공간을 소비함으로써 계산 속도를 높인다.

근사 알고리즘 분야에서는 다항 시간 내 해법이 존재하지 않는다고 여겨지는 일부 문제에 대해 이 방법을 적용하여, 의사 다항 시간 내에서 최적해를 얻을 수 있다.

2. 1. [[그리디 알고리즘]]과의 비교

그리디 알고리즘은 동적 계획법의 단점인 모든 가능성을 고려해야 하는 점을 극복하기 위해 등장했다. 그리디 알고리즘은 항상 최적해를 보장하지는 않지만, Minimum Spanning Tree(최소 신장 트리 문제) 등 여러 문제에서 최적해를 구할 수 있음이 입증되었다.

차량 정체 구간에서 A 지점에서 B 지점까지 가장 빠른 경로를 찾는 문제를 예로 들어 보자. 동적 계획법은 모든 가능한 경로와 교통 상황을 고려하여 최적의 경로를 찾는다. 반면 그리디 알고리즘은 전체 상황을 고려하지 않고, 순간마다 최선의 선택을 한다.

동적 계획법은 시간이 걸리지만, 교통 환경이 변하지 않는다면 가장 빠른 경로를 찾을 수 있다. 반면 그리디 알고리즘은 빠르지만, 항상 최적의 경로를 보장하지는 않는다. 각 구간에서 최적의 경로를 선택해도 전체적으로 최적이 아닐 수 있기 때문이다. 따라서 동적 계획법은 그리디 알고리즘보다 시간 효율성은 떨어질 수 있지만, 더 정확한 결과를 얻을 수 있다.

3. 구현 방법

동적 계획법은 다음 두 가지 방식으로 구현할 수 있다.


  • 하향식 (Top-Down) 접근 방식


큰 문제에서 작은 문제로 내려가면서 해를 구하는 방식이다. 분할 정복법에서 계산 결과를 기록하여 재사용한다. 재귀를 병용하는 경우 '''메모이제이션 재귀'''(memoized recursion영어)라고도 불린다.

  • 상향식 (Bottom-Up) 접근 방식


반복문을 사용하여 작은 문제부터 차례대로 해결하고, 그 결과를 이용하여 더 큰 문제의 해를 구하는 방법이다. 작은 문제에서 큰 문제로 올라가면서 해를 구한다.

상향식 방식은 먼저 부분 문제를 풀어가는 방법이다.

3. 1. 하향식 (Top-Down) 접근 방식

하향식 접근 방식은 큰 문제에서 작은 문제로 내려가면서 해를 구하는 방식이다. 분할 정복법에서 계산 결과를 기록하여 재사용한다. 재귀를 병용하는 경우 '''메모이제이션 재귀'''(memoized recursion영어)라고도 불린다.

3. 2. 상향식 (Bottom-Up) 접근 방식

상향식 접근 방식은 반복문을 사용하여 작은 문제부터 차례대로 해결하고, 그 결과를 이용하여 더 큰 문제의 해를 구하는 방법이다. 작은 문제에서 큰 문제로 올라가면서 해를 구한다.




상향식 방식은 먼저 부분 문제를 풀어가는 방법이다.

4. 적용 조건

최적화 문제에 적용하는 경우, 일반적으로 다음 두 가지가 적용되는 문제에 성립해야 한다. (엄밀하게는 성립하지 않아도 동적 계획법의 정의는 충족할 수 있다.)


  • '''부분 구조 최적성'''(옵티멀 서브스트럭처/optimal substructure영어) 또는 '''최적성의 원리'''(프린시플 오브 옵티말리티/principle of optimality영어)[22]
  • '''부분 문제 중복성'''(오버래핑 서브프라블럼스/overlapping subproblems영어)


부분 구조 최적성이란 다음 두 조건이 성립하는 것을 의미한다.

# 부분 문제도 동일한 최적화 문제가 성립한다.

# 부분 문제 간에 독립적이다.

부분 문제를 풀고, 이를 이용하여 전체 최적화 문제를 푸는 전략을 사용하기 때문에, 부분 구조 최적성은 동적 계획법에 필요하다. 부분 구조 최적성의 예시로, 최단 경로 문제에서 A → B → C라는 최단 경로에서 A → B 및 B → C도 최단 경로여야 한다(이는 귀류법으로 증명 가능하다). 또한, 부분 문제 간에 독립적이기 위해서는 부분 문제에서 자원 공유가 없어야 한다. 최단 경로 문제에서는 A → B와 B → C에서 동일한 변이 나타나지 않기 때문에(마찬가지로 귀류법으로 증명 가능), 자원 공유가 발생하지 않는다. 탐욕법에서도 엄밀한 해를 구하려면 부분 구조 최적성이 필요하다.

부분 문제 중복성이란 동일한 부분 문제가 반복적으로 나타나는 것이다. 동적 계획법에서는 중복되는 부분 문제의 계산 결과를 기록하고 재사용함으로써 계산량을 줄인다.

엄밀하게 말하면, 전체 문제와 부분 문제는 완전히 동일할 필요는 없으며, 부분 문제 간에 독립적이지 않더라도, 이들이 어떤 계산식을 통해 의존 관계를 해결하고 결합하는 방법이 있다면, 부분 구조 최적성이 성립하지 않아도 동적 계획법의 정의를 만족하는 알고리즘을 만들 수 있다. 그러나, 그러한 실용적인 예는 드물다.

4. 1. 부분 구조 최적성 (Optimal Substructure)

부분 구조 최적성은 전체 문제의 최적해가 부분 문제의 최적해를 포함하는 경우를 의미한다.[22] 예를 들어 최단 경로 문제에서 A → B → C의 최단 경로는 A → B와 B → C의 최단 경로를 포함한다. 이는 귀류법으로 증명 가능하다.[22]

부분 구조 최적성은 다음 두 조건이 성립해야 한다.

  • 부분 문제도 동일한 최적화 문제가 성립한다.
  • 부분 문제 간에 독립적이다.


부분 문제를 풀고 이를 이용하여 전체 최적화 문제를 푸는 전략을 사용하기 때문에 부분 구조 최적성은 동적 계획법에 필요하다. 최단 경로 문제에서는 A → B와 B → C에서 동일한 변이 나타나지 않기 때문에 부분 문제 간 자원 공유가 발생하지 않아 독립적이다. (이 역시 귀류법으로 증명 가능) 탐욕법에서도 엄밀한 해를 구하려면 부분 구조 최적성이 필요하다.[22]

4. 2. 부분 문제 중복성 (Overlapping Subproblems)

부분 문제 중복성이란 동일한 부분 문제가 반복적으로 나타나는 것을 의미한다.[22] 동적 계획법은 중복되는 부분 문제의 계산 결과를 저장하고 재사용하여 계산량을 줄인다.

5. 역사

리처드 벨만이 1940년대에 "동적 계획법(dynamic programming)"이라는 용어를 처음 사용했으며, 1953년에 현재의 정의가 확립되었다.[16] 벨만은 그의 자서전에서 "동적 계획법"이라는 용어의 배경을 설명했다.

벨만에 따르면, 1950년대는 수학 연구에 좋은 환경이 아니었다. 당시 국방장관이었던 윌슨은 "연구"라는 단어에 병적인 혐오감을 가지고 있었기 때문에, RAND 연구소 소속이었던 벨만은 연구 활동을 숨겨야 했다.[17]

이에 벨만은 "동적(Dynamic)"이라는 단어가 문제의 시가변적이며 다단계적인 특성을 나타내고,[17] "계획법(Programming)"이 당시 공군에서 훈련 및 물류 계획 등에 사용되던 용어였기 때문에 선택했다고 밝혔다.[18] 이는 선형 계획법이나 수리 계획법과 같이 수학적 최적화 기법을 의미한다.[18]

그러나 벨만이 이 용어를 처음 사용한 논문(1952)이 윌슨이 국방장관이 된 1953년보다 আগে 나왔기 때문에, 이 설명이 완전히 정확하지 않을 수 있다는 주장도 있다.[19] 해럴드 J. 쿠쉬너는 벨만이 단치히의 선형 계획법을 능가하기 위해 "동적"이라는 단어를 추가했다는 말을 들었다고 전하며, 두 가지 동기가 모두 작용했을 가능성을 제시했다.[20]

IEEE는 동적 계획법 분야를 시스템 분석 및 공학 주제로 인정했으며,[16] 벨만의 공헌은 벨만 방정식이라는 이름으로 기억되고 있다. 벨만 방정식은 최적화 문제를 재귀적 형태로 재진술하는 동적 계획법의 핵심 결과이다.[16]

6. 예제

피보나치 수열은 제 n항의 값이 제 n - 1항과 제 n - 2항의 합이 되는 수열이다. 이 문제는 최적화 문제가 아니다.

'''정의를 직접 구현한 프로그램'''

정의에 따라 피보나치 수열을 구하는 프로그램을 작성하면 다음과 같다.

```c

int fib(unsigned int n) {

switch (n) {

case 0: return 0;

case 1: return 1;

default: return fib(n - 1) + fib(n - 2);

}

}

```

예를 들어, 이 프로그램을 사용하여 피보나치 수열의 제5항을 구하는 경우를 생각해 보자. 이 프로그램은 재귀 호출되므로, 그 모습을 다음과 같이 나타낸다.

fib(5)

= fib(4) + fib(3)

= (fib(3) + fib(2)) + (fib(2) + fib(1))

= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

= (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

이처럼 최종적으로 fib(0)과 fib(1)의 호출로 수렴하며, fib(0)과 fib(1)의 호출 횟수의 합이 결과 값이 된다. 이 방법을 사용한 피보나치 수열의 계산량은 O(2^n)의 지수 시간이 된다. 이는 중복 계산이 많아 비효율적이다.

'''동적 계획법을 이용한 프로그램 (상향식)'''

반복문과 배열을 사용하여 작은 문제부터 해결해 나가면서 피보나치 수열을 계산한다. (계산 복잡도: O(n))



int fib(unsigned int n) {

int memo[1000] = {0, 1}, i;

for (i = 2; i <= n; i++) {

memo[i] = memo[i - 1] + memo[i - 2];

}

return memo[n];

}



fib(n - 1)과 fib(n - 2)를 먼저 계산한 다음 fib(n)을 계산한다. 이 경우 앞서 구현한 방식과는 달리 루프 부분의 계산량은 ''O''(n)의 다항 시간이다. 이처럼 지수 시간으로 수행되는 처리를, 계산된 결과를 기록함으로써 다항 시간으로 처리하도록 개선하여 계산 시간을 압도적으로 줄일 수 있다.

'''동적 계획법을 이용한 프로그램 (하향식)'''

탑다운 방식이며, 메모이제이션을 병용하는 방법이다. `fib(n)`을 계산하기 위해 `fib(n - 1)`과 `fib(n - 2)`가 필요하지만, 계산 결과를 배열 `memo`에 저장하여 재사용한다.

```c

#include

int memo[1000] = {0, 1};

bool in_memo[1000] = {true, true};

int fib(unsigned int n) {

if (!in_memo[n]) {

memo[n] = fib(n - 1) + fib(n - 2);

in_memo[n] = true;

}

return memo[n];

}

```

최근에는 다양한 프로그래밍 언어가 메모이제이션을 언어 수준에서 지원하고 있다. 해당 기능을 이용하면 더 간단하게 작성할 수 있는 경우가 있다. 예를 들어 Groovy의 경우, `@Memoized`를 붙임으로써 메모이제이션을 수행하는데, 아래와 같이 정의를 직접 구현한 프로그램에 `@Memoized`를 붙이면 동적 계획법이 된다.

```groovy

import groovy.transform.Memoized

@Memoized

int fib(int n) {

switch (n) {

case 0: return 0;

case 1: return 1;

default: return fib(n - 1) + fib(n - 2);

}

}

```

'''0-1 행렬 문제'''

짝수 n에 대해, 각 행과 열에 정확히 n/2개의 0과 n/2개의 1을 포함하는 n x n 행렬의 개수를 구하는 문제이다. 예를 들어, n = 4일 때, 가능한 해는 다음과 같다.

:\begin{bmatrix}

0 & 1 & 0 & 1 \\

1 & 0 & 1 & 0 \\

0 & 1 & 0 & 1 \\

1 & 0 & 1 & 0

\end{bmatrix} \text{ and } \begin{bmatrix}

0 & 0 & 1 & 1 \\

0 & 0 & 1 & 1 \\

1 & 1 & 0 & 0 \\

1 & 1 & 0 & 0

\end{bmatrix} \text{ and } \begin{bmatrix}

1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1 \\

1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1

\end{bmatrix} \text{ and } \begin{bmatrix}

1 & 0 & 0 & 1 \\

0 & 1 & 1 & 0 \\

0 & 1 & 1 & 0 \\

1 & 0 & 0 & 1

\end{bmatrix} \text{ and } \begin{bmatrix}

1 & 1 & 0 & 0 \\

1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1 \\

0 & 0 & 1 & 1

\end{bmatrix}.

이 문제를 해결하기 위한 접근 방식에는 무차별 대입법, 백트래킹, 동적 계획법이 있다.


  • 무차별 대입법: 0과 1의 모든 할당을 확인하고 균형 잡힌 행과 열(n/2개의 0과 n/2개의 1)을 가진 것들을 센다. 가능한 할당이 2^{n^2}개이고, 합리적인 할당이 \tbinom{n}{n/2}^n개이므로, 이 전략은 최대 n=6까지는 실용적이지 않다.

  • 백트래킹: 행렬 요소의 순서를 선택하고 1 또는 0을 재귀적으로 배치하며, 모든 행과 열에서 할당되지 않은 요소의 수와 1 또는 0의 수가 모두 최소 n/2 이상인지 확인한다. 무차별 대입법보다 정교하지만, 이 접근 방식은 모든 해를 한 번씩 방문하므로 해의 수가 n이 6보다 큰 경우에는 실용적이지 않다.


동적 계획법은 모든 해를 방문하지 않고도 해의 수를 계산할 수 있게 해준다. 1 ≤ k ≤ n인 k x n 보드를 고려하는데, 여기서 k개의 행은 n/2개의 0과 n/2개의 1을 포함한다. 메모이제이션이 적용되는 함수 ''f''는 정수 쌍의 ''n'' 벡터를 허용 가능한 보드(해)의 수에 매핑한다. 각 열마다 한 쌍이 있으며, 해당 열에 아직 배치되지 않은 0과 1의 수를 각각 나타낸다. 우리는 f((n/2, n/2), (n/2, n/2), \ldots (n/2, n/2)) (n개의 인자 또는 n개의 요소 벡터)의 값을 구한다. 부분 문제 생성 과정은 보드의 맨 위 행에 대한 \tbinom{n}{n/2}개의 가능한 할당을 모두 반복하고 각 열을 거쳐, 맨 위 행의 할당에 해당 위치에 0 또는 1이 있었는지에 따라 해당 열의 쌍의 적절한 요소에서 1을 뺀다. 결과 중 하나라도 음수이면 해당 할당은 유효하지 않으며 해 집합에 기여하지 않는다(재귀가 중단됨). 그렇지 않으면, k x n 보드의 맨 위 행에 대한 할당을 갖고 나머지 (k - 1) x n 보드에 대한 해의 수를 재귀적으로 계산하여, 맨 위 행의 각 허용 가능한 할당에 대한 해의 수를 더하고 합계를 반환하는데, 이는 메모이제이션되고 있다. 기본 경우는 1 x n 보드에서 발생하는 사소한 부분 문제이다. 이 보드에 대한 해의 수는 벡터가 n / 2개의 (0, 1)과 n / 2개의 (1, 0) 쌍의 순열인지 여부에 따라 0 또는 1이다.

해의 수 는 다음과 같다.

: 1,\, 2,\, 90,\, 297200,\, 116963796250,\, 6736218287430460752, \ldots

'''하노이의 탑'''

'''하노이의 탑''' 또는 '''하노이 탑'''은 세 개의 막대와 크기가 다른 여러 개의 원반으로 구성된 수학 게임 또는 퍼즐이다. 퍼즐은 크기 순서대로 오름차순으로 정렬된 원반이 하나의 막대에 쌓여있는 상태로 시작하며, 가장 작은 원반이 맨 위에 놓여 원뿔 모양을 이룬다.

퍼즐의 목표는 다음 규칙을 준수하면서 전체 스택을 다른 막대로 옮기는 것이다.

  • 한 번에 하나의 원반만 옮길 수 있다.
  • 각 이동은 막대 중 하나에서 맨 위에 있는 원반을 꺼내 다른 막대 위에 놓는 것으로 구성되며, 해당 막대에 이미 다른 원반이 있을 수 있다.
  • 더 작은 원반 위에 더 큰 원반을 놓을 수 없다.


동적 프로그래밍 솔루션은 다음 함수 방정식을 푸는 것으로 구성된다.[12]

: S(n,h,t) = S(n-1,h, not(h,t)) ; S(1,h,t) ; S(n-1,not(h,t),t)

여기서 n은 이동할 원반의 수를 나타내고, h는 시작 막대를 나타내며, t는 목표 막대를 나타내고, not(h,t)는 세 번째 막대(h도 t도 아님)를 나타내며, ";"는 연결을 나타낸다.[12]

: S(n, h, t) := n개의 원반으로 구성된 문제에 대한 해결책으로, 막대 h에서 막대 t로 옮겨야 한다.

n=1인 경우 문제는 자명하며, S(1,h,t) = "막대 h에서 막대 t로 원반을 이동" (원반이 하나만 남음)이다.[12]

이 해결책에 필요한 이동 횟수는 2''n'' − 1이다. 목표가 이동 횟수를 '''최대화'''하는 것일 경우(순환 없이) 동적 프로그래밍 함수 방정식은 약간 더 복잡하며, 3''n'' − 1 이동이 필요하다.[12]

'''행렬 곱셈 순서 문제'''

행렬 연쇄 곱셈은 동적 계획법의 유용성을 보여주는 잘 알려진 예시이다. 예를 들어, 공학 응용 프로그램에서는 종종 행렬의 연쇄를 곱해야 한다. 100×100과 같은 큰 차원의 행렬을 찾는 것은 놀라운 일이 아니다. 행렬 곱셈은 교환 법칙이 성립하지 않지만 결합 법칙은 성립한다. 또한 한 번에 두 개의 행렬만 곱할 수 있다. 따라서 행렬의 연쇄를 여러 가지 방법으로 곱할 수 있는데, 모두 동일한 최종 결과를 생성하지만 어떤 특정 행렬을 곱하는지에 따라 계산 시간이 더 오래 걸리거나 덜 걸린다.

예를 들어, 행렬 A, B 및 C를 곱해 보자. 차원이 각각 m×n, n×p 및 p×s라고 가정해 보자. 행렬 Ax(B×C)는 nps + mns 개의 스칼라 곱셈이 필요하고 (A×B)×C는 mnp + mps 개의 스칼라 계산이 필요하다. m = 10, n = 100, p = 10, s = 1000이라고 가정하면, 첫 번째 방법은 1,000,000 + 1,000,000번의 계산이 필요하고 두 번째 방법은 10,000+100,000번의 계산만 필요하므로 두 번째 방법이 더 빠르다.

따라서 괄호의 순서가 중요하며, 주어진 행렬들의 곱셈 순서를 최소화하는 것이 이 문제의 목표이다. 이 문제는 중첩되는 부분 문제로 분할하고 동적 계획법 알고리즘을 설계하여 괄호의 최적 배열을 계산할 수 있다.

''n'' × ''n''개의 사각형으로 이루어진 체스판을 고려하고, 사각형 (i,j)와 관련된 비용을 반환하는 비용 함수 c(i, j)를 고려합니다(''i''는 행, ''j''는 열). 예를 들어 (5 × 5 체스판에서),

567478
476114
335782
2–670–
1––5––
width="15"|12345



따라서 c(1, 3) = 5

첫 번째 랭크(즉, 행)의 임의의 사각형에서 시작할 수 있는 체커가 있고 마지막 랭크에 도달하는 최단 경로(각 방문된 랭크에서 최소 비용의 합)를 알고 싶다고 가정합니다. 체커가 대각선 왼쪽 앞으로, 대각선 오른쪽 앞으로, 또는 앞으로만 이동할 수 있다고 가정합니다. 즉, (1,3)의 체커는 (2,2), (2,3) 또는 (2,4)로 이동할 수 있습니다.

5
4
3
2xxx
1o
width="15"|12345



이 문제는 '''최적 부분 구조'''를 나타냅니다. 즉, 전체 문제에 대한 해결책은 부분 문제에 대한 해결책에 의존합니다. 다음과 같이 함수 q(i, j)를 정의합니다.

:''q''(''i'', ''j'') = 사각형 (''i'', ''j'')에 도달하는 최소 비용.

랭크 n에서 시작하여 랭크 1로 내려가면서 각 연속 랭크에서 모든 사각형에 대해 이 함수의 값을 계산합니다. 각 랭크에서 최소값을 갖는 사각형을 선택하면 랭크 n과 랭크 1 사이의 최단 경로가 제공됩니다.

함수 q(i, j)는 아래에 있는 세 개의 사각형 중 어느 곳이든 도달하는 최소 비용(도달할 수 있는 유일한 사각형) 더하기 c(i, j)와 같습니다. 예를 들어,

5
4A
3BCD
2
1
width="15"|12345



:q(A) = \min(q(B),q(C),q(D))+c(A) \,

이제 q(i, j)를 다소 일반적인 용어로 정의해 보겠습니다.

:q(i,j)=\begin{cases} \infty & j < 1 \text{ or }j > n \\ c(i, j) & i = 1 \\ \min(q(i-1, j-1), q(i-1, j), q(i-1, j+1)) + c(i,j) & \text{otherwise.}\end{cases}

유전학에서, 서열 정렬(sequence alignment)은 동적 계획법이 필수적인 중요한 응용 분야이다.[17] 일반적으로 이 문제는 하나의 서열을 요소의 교체, 삽입 또는 제거와 같은 편집 연산을 사용하여 다른 서열로 변환하는 것으로 구성된다. 각 연산에는 연관된 비용이 있으며, 목표는 총 비용이 가장 낮은 일련의 편집(sequence of edits)을 찾는 것이다.

문제는 자연스럽게 재귀로 표현될 수 있는데, 서열 A는 다음과 같은 방법으로 서열 B로 최적으로 편집된다.

# B의 첫 번째 문자를 삽입하고, A와 B의 꼬리에 대한 최적 정렬을 수행한다.

# A의 첫 번째 문자를 삭제하고, A의 꼬리와 B에 대한 최적 정렬을 수행한다.

# A의 첫 번째 문자를 B의 첫 번째 문자로 바꾸고, A와 B의 꼬리에 대한 최적 정렬을 수행한다.

부분 정렬은 행렬로 표로 나타낼 수 있으며, 여기서 셀 (i,j)는 A[1..i]에서 B[1..j]까지의 최적 정렬 비용을 포함한다. 셀 (i,j)의 비용은 관련 연산의 비용을 인접한 셀의 비용에 더하고 최적값을 선택하여 계산할 수 있다.

다양한 변형이 존재하며, 스미스-워터만 알고리즘(Smith–Waterman algorithm)과 니들만-분쉬 알고리즘(Needleman–Wunsch algorithm)을 참조하라.

다음은 N=2개의 달걀과 H=36층짜리 건물과 관련된 이 유명한 퍼즐의 사례에 대한 설명입니다:[13]

: 36층 건물에서 달걀을 떨어뜨려도 안전한 층과 착지 시 달걀이 깨지는 층을 알고 싶다고 가정해 봅시다 (미국식 영어 용어 사용, 1층은 지면과 같음). 몇 가지 가정을 합니다.

: * 낙하를 견딘 달걀은 다시 사용할 수 있습니다.

: * 깨진 달걀은 버려야 합니다.

: * 낙하의 효과는 모든 달걀에 동일합니다.

: * 달걀이 떨어져 깨지면 더 높은 창문에서 떨어뜨려도 깨집니다.

: * 달걀이 낙하를 견디면 더 짧은 낙하도 견딜 것입니다.

: * 1층 창문에서 달걀이 깨질 수도 있고 36층 창문에서 달걀이 견딜 수도 있습니다.

: 달걀이 하나만 있고 올바른 결과를 얻고 싶다면 실험은 한 가지 방법으로만 수행할 수 있습니다. 1층 창문에서 달걀을 떨어뜨립니다. 깨지지 않으면 2층 창문에서 떨어뜨립니다. 깨질 때까지 위로 계속합니다. 최악의 경우 이 방법은 36번의 낙하가 필요할 수 있습니다. 달걀이 2개 있다고 가정해 봅시다. 모든 경우에 작동이 보장되는 달걀 낙하 횟수의 최솟값은 얼마입니까?

이 퍼즐에 대한 동적 프로그래밍 함수 방정식을 유도하기 위해 동적 프로그래밍 모델의 '''상태'''를 s = (n,k) 쌍으로 정의합니다. 여기서

: ''n'' = 사용할 수 있는 테스트 달걀의 수, ''n'' = 0, 1, 2, 3, ..., ''N'' − 1.

: ''k'' = 아직 테스트해야 하는 (연속적인) 층의 수, ''k'' = 0, 1, 2, ..., ''H'' − 1.

예를 들어, ''s'' = (2,6)은 테스트 달걀이 2개 있고 6 (연속적인) 층을 아직 테스트해야 함을 나타냅니다. 프로세스의 초기 상태는 ''s'' = (''N'',''H'')이며 여기서 ''N''은 실험 시작 시 사용할 수 있는 테스트 달걀의 수를 나타냅니다. 프로세스는 더 이상 테스트 달걀이 없거나 (''n'' = 0) ''k'' = 0일 때 종료되며, 둘 중 먼저 발생하는 조건에 따라 종료됩니다. 종료가 상태 ''s'' = (0,''k'')에서 발생하고 ''k'' > 0인 경우 테스트에 실패한 것입니다.

이제,

: ''W''(''n'',''k'') = 최악의 경우에 임계 층의 값을 식별하는 데 필요한 최소 시행 횟수이며, 프로세스가 상태 ''s'' = (''n'',''k'')에 주어져 있습니다.

그러면 다음과 같이 나타낼 수 있습니다.[14]

: ''W''(''n'',''k'') = 1 + min{max(''W''(''n'' − 1, ''x'' − 1), ''W''(''n'',''k'' − ''x'')): ''x'' = 1, 2, ..., ''k'' }

여기서 모든 ''n'' > 0에 대해 ''W''(''n'',0) = 0이고 모든 ''k''에 대해 ''W''(1,''k'') = ''k''입니다. 이 방정식을 체계적으로 ''n''과 ''k''의 값을 증가시켜 반복적으로 푸는 것은 쉽습니다.

위의 해법은 동적 계획법을 사용하여 O( n k^2 ) 시간이 걸린다는 것을 알 수 있습니다. 이 방법은 위의 재귀식에서 최적의 x에 대해 이진 탐색을 수행하여 O( n k \log k ) 시간으로 개선할 수 있습니다. 왜냐하면 W(n-1,x-1)는 x에 대해 증가하는 반면 W(n,k-x)는 x에 대해 감소하므로 \max(W(n-1,x-1),W(n,k-x))의 지역 최소값은 전체 최소값이기 때문입니다. 또한, 동적 계획법 표의 각 셀에 대한 최적의 x를 저장하고 이전 셀의 값을 참조함으로써, 각 셀에 대한 최적의 x를 상수 시간에 찾을 수 있으며, 이를 통해 O( n k ) 시간으로 개선할 수 있습니다. 하지만 문제의 다른 매개변수화를 포함하는 훨씬 더 빠른 해법이 있습니다.

k를 k번째 층에서 떨어뜨릴 때 계란이 깨지는 총 층 수라고 합니다(위의 예는 k=37로 하는 것과 동일합니다).

m을 계란이 깨지도록 떨어뜨려야 하는 최소 층이라고 합니다.

f(t,n)을 t번의 시도와 n개의 계란을 사용하여 구별할 수 있는 m의 최대 값이라고 합니다.

그러면 모든 t,n \geq 0에 대해 f(t,0) = f(0,n) = 1입니다.

a를 최적의 전략에서 첫 번째 계란을 떨어뜨리는 층이라고 합니다.

첫 번째 계란이 깨지면 m은 1부터 a까지이며 최대 t-1번의 시도와 n-1개의 계란을 사용하여 구별할 수 있습니다.

첫 번째 계란이 깨지지 않으면 m은 a+1부터 k까지이며 t-1번의 시도와 n개의 계란을 사용하여 구별할 수 있습니다.

따라서 f(t,n) = f(t-1,n-1) + f(t-1,n)입니다.

그러면 문제는 f(x,n) \geq k를 만족하는 최소 x를 찾는 것과 같습니다.

이를 위해 t를 증가하는 순서로 \{ f(t,i) : 0 \leq i \leq n \}을 계산할 수 있으며, 이는 O( n x ) 시간이 걸립니다.

따라서 n=1의 경우를 별도로 처리하면 알고리즘은 O( n \sqrt{k} ) 시간이 걸립니다.

하지만 실제로 재귀 관계를 풀 수 있으며, f(t,n) = \sum_{i=0}^{n}{ \binom{t}{i} }를 얻을 수 있습니다. 이는 모든 i \geq 0에 대해 항등식 \binom{t}{i+1} = \binom{t}{i} \frac{t-i}{i+1}을 사용하여 O(n) 시간에 계산할 수 있습니다.

모든 t \geq 0에 대해 f(t,n) \leq f(t+1,n)이므로 t에 대해 이진 탐색하여 x를 찾을 수 있으며, 이는 O( n \log k ) 알고리즘을 제공합니다.[15]

6. 1. [[피보나치 수열]]

피보나치 수열은 제 n항의 값이 제 n - 1항과 제 n - 2항의 합이 되는 수열이다. 이 문제는 최적화 문제가 아니다.

보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.



int fib(unsigned int n) {

switch (n) {

case 0: return 0;

case 1: return 1;

default: return fib(n - 1) + fib(n - 2);

}

}



예를 들어, 이 프로그램을 사용하여 피보나치 수열의 제5항을 구하는 경우를 생각해 보자. 이 프로그램은 재귀 호출되므로, 그 모습을 다음과 같이 나타낸다.

fib(5)

= fib(4) + fib(3)

= (fib(3) + fib(2)) + (fib(2) + fib(1))

= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

= (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

이처럼 최종적으로 fib(0)과 fib(1)의 호출로 수렴하며, fib(0)과 fib(1)의 호출 횟수의 합이 결과 값이 된다. 이 방법을 사용한 피보나치 수열의 계산량은 O(2^n)의 지수 시간이 된다. 이는 중복 계산이 많아 비효율적이다. 특히 fib(2)는 처음부터 세 번 계산되었다. 더 큰 예제에서는 fib 또는 "부분 문제"의 값이 훨씬 더 많이 재계산되어 지수 시간 알고리즘이 된다.

동적 계획법을 사용하여 피보나치 수열의 ''n''번째 항을 계산하면 성능이 크게 향상된다.

이제 이미 계산된 각 fib 값을 해당 결과에 매핑하는 간단한 맵 객체 ''m''이 있다고 가정하고 이를 사용하고 업데이트하도록 함수를 수정한다. 결과 함수는 지수 시간 대신 O(''n'') 시간만 필요합니다(하지만 O(''n'') 공간 필요):

'''var''' m := '''''map'''''(0 → 0, 1 → 1)

'''function''' fib(n)

'''if ''key''''' n '''is not in ''map''''' m

m[n] := fib(n − 1) + fib(n − 2)

'''return''' m[n]

이미 계산된 값을 저장하는 이 기술을 ''메모이제이션''이라고 한다. 이는 먼저 문제를 하위 문제로 나누고 값을 계산하고 저장하기 때문에 상향식 접근 방식이다.

'''하향식''' 접근 방식에서는 먼저 fib의 작은 값을 계산한 다음 이를 기반으로 더 큰 값을 구축한다. 이 방법은 n − 1번 반복되는 루프를 포함하므로 O(''n'') 시간을 사용하지만, 맵을 저장하는 O(''n'') 공간이 필요한 상향식 접근 방식과 달리 상수(O(1)) 공간만 사용한다.

'''function''' fib(n)

'''if''' n = 0

'''return''' 0

'''else'''

'''var''' previousFib := 0, currentFib := 1

'''repeat''' n − 1 '''times''' ''// loop is skipped if n = 1''

'''var''' newFib := previousFib + currentFib

previousFib := currentFib

currentFib := newFib

'''return''' currentFib

두 예제 모두에서 fib(2)를 한 번만 계산한 다음 이를 사용하여 fib(4)와 fib(3)을 모두 계산한다. 두 값 중 하나를 평가할 때마다 계산하는 대신 말이다.

탑다운 방식이며, 메모이제이션을 병용하는 방법이다. `fib(n)`을 계산하기 위해 `fib(n - 1)`과 `fib(n - 2)`가 필요하지만, 계산 결과를 배열 `memo`에 저장하여 재사용한다.

```c

#include

int memo[1000] = {0, 1};

bool in_memo[1000] = {true, true};

int fib(unsigned int n) {

if (!in_memo[n]) {

memo[n] = fib(n - 1) + fib(n - 2);

in_memo[n] = true;

}

return memo[n];

}

```

최근에는 다양한 프로그래밍 언어가 메모이제이션을 언어 수준에서 지원하고 있다. 해당 기능을 이용하면 더 간단하게 작성할 수 있는 경우가 있다. 예를 들어 Groovy의 경우, `@Memoized`를 붙임으로써 메모이제이션을 수행하는데, 아래와 같이 정의를 직접 구현한 프로그램에 `@Memoized`를 붙이면 동적 계획법이 된다.

```groovy

import groovy.transform.Memoized

@Memoized

int fib(int n) {

switch (n) {

case 0: return 0

case 1: return 1

default: return fib(n - 1) + fib(n - 2)

}

}

```

반복문과 배열을 사용하여 작은 문제부터 해결해 나가면서 피보나치 수열을 계산한다. (계산 복잡도: O(n))



int fib(unsigned int n) {

int memo[1000] = {0, 1}, i;

for (i = 2; i <= n; i++) {

memo[i] = memo[i - 1] + memo[i - 2];

}

return memo[n];

}



fib(n - 1)과 fib(n - 2)를 먼저 계산한 다음 fib(n)을 계산한다. 이 경우 앞서 구현한 방식과는 달리 루프 부분의 계산량은 ''O''(n)의 다항 시간이다. 이처럼 지수 시간으로 수행되는 처리를, 계산된 결과를 기록함으로써 다항 시간으로 처리하도록 개선하여 계산 시간을 압도적으로 줄일 수 있다.

6. 1. 1. 정의를 직접 구현한 프로그램

정의에 따라 피보나치 수열을 구하는 프로그램을 작성하면 다음과 같다.

```c

int fib(unsigned int n) {

switch (n) {

case 0: return 0;

case 1: return 1;

default: return fib(n - 1) + fib(n - 2);

}

}

```

예를 들어, 이 프로그램을 사용하여 피보나치 수열의 제5항을 구하는 경우를 생각해 보자. 이 프로그램은 재귀 호출되므로, 그 모습을 다음과 같이 나타낸다.

fib(5)

= fib(4) + fib(3)

= (fib(3) + fib(2)) + (fib(2) + fib(1))

= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

= (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

이처럼 최종적으로 fib(0)과 fib(1)의 호출로 수렴하며, fib(0)과 fib(1)의 호출 횟수의 합이 결과 값이 된다. 이 방법을 사용한 피보나치 수열의 계산량은 O(2^n)의 지수 시간이 된다. 이는 중복 계산이 많아 비효율적이다.

6. 1. 2. 동적 계획법을 이용한 프로그램 (상향식)

wikitext

반복문과 배열을 사용하여 작은 문제부터 해결해 나가면서 피보나치 수열을 계산한다. (계산 복잡도: O(n))



int fib(unsigned int n) {

int memo[1000] = {0, 1}, i;

for (i = 2; i <= n; i++) {

memo[i] = memo[i - 1] + memo[i - 2];

}

return memo[n];

}



fib(n - 1)과 fib(n - 2)를 먼저 계산한 다음 fib(n)을 계산한다. 이 경우 앞서 구현한 방식과는 달리 루프 부분의 계산량은 ''O''(n)의 다항 시간이다. 이처럼 지수 시간으로 수행되는 처리를, 계산된 결과를 기록함으로써 다항 시간으로 처리하도록 개선하여 계산 시간을 압도적으로 줄일 수 있다.

6. 1. 3. 동적 계획법을 이용한 프로그램 (하향식)

탑다운 방식이며, 메모이제이션을 병용하는 방법이다. `fib(n)`을 계산하기 위해 `fib(n - 1)`과 `fib(n - 2)`가 필요하지만, 계산 결과를 배열 `memo`에 저장하여 재사용한다.

```c

#include

int memo[1000] = {0, 1};

bool in_memo[1000] = {true, true};

int fib(unsigned int n) {

if (!in_memo[n]) {

memo[n] = fib(n - 1) + fib(n - 2);

in_memo[n] = true;

}

return memo[n];

}

```

최근에는 다양한 프로그래밍 언어가 메모이제이션을 언어 수준에서 지원하고 있다. 해당 기능을 이용하면 더 간단하게 작성할 수 있는 경우가 있다. 예를 들어 Groovy의 경우, `@Memoized`를 붙임으로써 메모이제이션을 수행하는데, 아래와 같이 정의를 직접 구현한 프로그램에 `@Memoized`를 붙이면 동적 계획법이 된다.

```groovy

import groovy.transform.Memoized

@Memoized

int fib(int n) {

switch (n) {

case 0: return 0

case 1: return 1

default: return fib(n - 1) + fib(n - 2)

}

}

6. 2. 0-1 행렬 문제

짝수 n에 대해, 각 행과 열에 정확히 n/2개의 0과 n/2개의 1을 포함하는 n x n 행렬의 개수를 구하는 문제이다. 예를 들어, n = 4일 때, 가능한 해는 다음과 같다.

:\begin{bmatrix}

0 & 1 & 0 & 1 \\

1 & 0 & 1 & 0 \\

0 & 1 & 0 & 1 \\

1 & 0 & 1 & 0

\end{bmatrix} \text{ and } \begin{bmatrix}

0 & 0 & 1 & 1 \\

0 & 0 & 1 & 1 \\

1 & 1 & 0 & 0 \\

1 & 1 & 0 & 0

\end{bmatrix} \text{ and } \begin{bmatrix}

1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1 \\

1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1

\end{bmatrix} \text{ and } \begin{bmatrix}

1 & 0 & 0 & 1 \\

0 & 1 & 1 & 0 \\

0 & 1 & 1 & 0 \\

1 & 0 & 0 & 1

\end{bmatrix} \text{ and } \begin{bmatrix}

1 & 1 & 0 & 0 \\

1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1 \\

0 & 0 & 1 & 1

\end{bmatrix}.

이 문제를 해결하기 위한 접근 방식에는 무차별 대입법, 백트래킹, 동적 계획법이 있다.

  • 무차별 대입법: 0과 1의 모든 할당을 확인하고 균형 잡힌 행과 열(n/2개의 0과 n/2개의 1)을 가진 것들을 센다. 가능한 할당이 2^{n^2}개이고, 합리적인 할당이 \tbinom{n}{n/2}^n개이므로, 이 전략은 최대 n=6까지는 실용적이지 않다.

  • 백트래킹: 행렬 요소의 순서를 선택하고 1 또는 0을 재귀적으로 배치하며, 모든 행과 열에서 할당되지 않은 요소의 수와 1 또는 0의 수가 모두 최소 n/2 이상인지 확인한다. 무차별 대입법보다 정교하지만, 이 접근 방식은 모든 해를 한 번씩 방문하므로 해의 수가 n이 6보다 큰 경우에는 실용적이지 않다.


동적 계획법은 모든 해를 방문하지 않고도 해의 수를 계산할 수 있게 해준다. 1 ≤ k ≤ n인 k x n 보드를 고려하는데, 여기서 k개의 행은 n/2개의 0과 n/2개의 1을 포함한다. 메모이제이션이 적용되는 함수 ''f''는 정수 쌍의 ''n'' 벡터를 허용 가능한 보드(해)의 수에 매핑한다. 각 열마다 한 쌍이 있으며, 해당 열에 아직 배치되지 않은 0과 1의 수를 각각 나타낸다. 우리는 f((n/2, n/2), (n/2, n/2), \ldots (n/2, n/2)) (n개의 인자 또는 n개의 요소 벡터)의 값을 구한다. 부분 문제 생성 과정은 보드의 맨 위 행에 대한 \tbinom{n}{n/2}개의 가능한 할당을 모두 반복하고 각 열을 거쳐, 맨 위 행의 할당에 해당 위치에 0 또는 1이 있었는지에 따라 해당 열의 쌍의 적절한 요소에서 1을 뺀다. 결과 중 하나라도 음수이면 해당 할당은 유효하지 않으며 해 집합에 기여하지 않는다(재귀가 중단됨). 그렇지 않으면, k x n 보드의 맨 위 행에 대한 할당을 갖고 나머지 (k - 1) x n 보드에 대한 해의 수를 재귀적으로 계산하여, 맨 위 행의 각 허용 가능한 할당에 대한 해의 수를 더하고 합계를 반환하는데, 이는 메모이제이션되고 있다. 기본 경우는 1 x n 보드에서 발생하는 사소한 부분 문제이다. 이 보드에 대한 해의 수는 벡터가 n / 2개의 (0, 1)과 n / 2개의 (1, 0) 쌍의 순열인지 여부에 따라 0 또는 1이다.

해의 수 는 다음과 같다.

: 1,\, 2,\, 90,\, 297200,\, 116963796250,\, 6736218287430460752, \ldots

6. 3. 하노이 탑



'''하노이의 탑''' 또는 '''하노이 탑'''은 세 개의 막대와 크기가 다른 여러 개의 원반으로 구성된 수학 게임 또는 퍼즐이다. 퍼즐은 크기 순서대로 오름차순으로 정렬된 원반이 하나의 막대에 쌓여있는 상태로 시작하며, 가장 작은 원반이 맨 위에 놓여 원뿔 모양을 이룬다.

퍼즐의 목표는 다음 규칙을 준수하면서 전체 스택을 다른 막대로 옮기는 것이다.

  • 한 번에 하나의 원반만 옮길 수 있다.
  • 각 이동은 막대 중 하나에서 맨 위에 있는 원반을 꺼내 다른 막대 위에 놓는 것으로 구성되며, 해당 막대에 이미 다른 원반이 있을 수 있다.
  • 더 작은 원반 위에 더 큰 원반을 놓을 수 없다.


동적 프로그래밍 솔루션은 다음 함수 방정식을 푸는 것으로 구성된다.[12]

: S(n,h,t) = S(n-1,h, not(h,t)) ; S(1,h,t) ; S(n-1,not(h,t),t)

여기서 n은 이동할 원반의 수를 나타내고, h는 시작 막대를 나타내며, t는 목표 막대를 나타내고, not(h,t)는 세 번째 막대(h도 t도 아님)를 나타내며, ";"는 연결을 나타낸다.[12]

: S(n, h, t) := n개의 원반으로 구성된 문제에 대한 해결책으로, 막대 h에서 막대 t로 옮겨야 한다.

n=1인 경우 문제는 자명하며, S(1,h,t) = "막대 h에서 막대 t로 원반을 이동" (원반이 하나만 남음)이다.[12]

이 해결책에 필요한 이동 횟수는 2''n'' − 1이다. 목표가 이동 횟수를 '''최대화'''하는 것일 경우(순환 없이) 동적 프로그래밍 함수 방정식은 약간 더 복잡하며, 3''n'' − 1 이동이 필요하다.[12]

6. 4. 행렬 곱셈 순서 문제

행렬 연쇄 곱셈은 동적 계획법의 유용성을 보여주는 잘 알려진 예시이다. 예를 들어, 공학 응용 프로그램에서는 종종 행렬의 연쇄를 곱해야 한다. 100×100과 같은 큰 차원의 행렬을 찾는 것은 놀라운 일이 아니다. 행렬 곱셈은 교환 법칙이 성립하지 않지만 결합 법칙은 성립한다. 또한 한 번에 두 개의 행렬만 곱할 수 있다. 따라서 행렬의 연쇄를 여러 가지 방법으로 곱할 수 있는데, 모두 동일한 최종 결과를 생성하지만 어떤 특정 행렬을 곱하는지에 따라 계산 시간이 더 오래 걸리거나 덜 걸린다.

예를 들어, 행렬 A, B 및 C를 곱해 보자. 차원이 각각 m×n, n×p 및 p×s라고 가정해 보자. 행렬 Ax(B×C)는 nps + mns 개의 스칼라 곱셈이 필요하고 (A×B)×C는 mnp + mps 개의 스칼라 계산이 필요하다. m = 10, n = 100, p = 10, s = 1000이라고 가정하면, 첫 번째 방법은 1,000,000 + 1,000,000번의 계산이 필요하고 두 번째 방법은 10,000+100,000번의 계산만 필요하므로 두 번째 방법이 더 빠르다.

따라서 괄호의 순서가 중요하며, 주어진 행렬들의 곱셈 순서를 최소화하는 것이 이 문제의 목표이다. 이 문제는 중첩되는 부분 문제로 분할하고 동적 계획법 알고리즘을 설계하여 괄호의 최적 배열을 계산할 수 있다.

7. 동적 계획법을 이용한 알고리즘

7. 1. 컴퓨터 과학

동적 계획법이 적용되려면 문제에 최적 부분 구조와 겹치는 부분 문제라는 두 가지 핵심 속성이 있어야 한다. 만약 ''겹치지 않는'' 부분 문제의 최적 해를 결합하여 문제를 해결할 수 있다면, 그 전략은 "분할 정복"이라고 한다.[1] 이것이 병합 정렬과 퀵 정렬이 동적 계획법 문제로 분류되지 않는 이유이다.

''최적 부분 구조''는 주어진 최적화 문제의 해가 하위 문제의 최적 해를 결합하여 얻을 수 있음을 의미한다. 예를 들어, 그래프 ''G=(V,E)''가 주어졌을 때, 정점 ''u''에서 정점 ''v''까지의 최단 경로 ''p''는 최적 부분 구조를 나타낸다. 이 최단 경로 ''p''의 임의의 중간 정점 ''w''를 취한다. 만약 ''p''가 진정으로 최단 경로라면, 이 경로는 ''u''에서 ''w''까지의 부분 경로 ''p1''과 ''w''에서 ''v''까지의 부분 경로 ''p2''로 분할될 수 있으며, 이 부분 경로들은 해당 정점들 사이의 진정한 최단 경로이다. 따라서, 최단 경로를 찾는 해를 재귀적으로 쉽게 공식화할 수 있으며, 이것이 벨만-포드 알고리즘 또는 플로이드-워셜 알고즘이 하는 일이다.

''겹치는'' 부분 문제는 부분 문제의 공간이 작아야 함을 의미한다. 즉, 문제를 해결하는 임의의 재귀 알고리즘은 새로운 부분 문제를 생성하기보다는 동일한 부분 문제를 반복해서 해결해야 한다. 예를 들어, 피보나치 수열을 생성하기 위한 재귀적 공식을 생각해 보자. ''F''''i'' = ''F''''i''−1 + ''F''''i''−2, 기저 사례는 ''F''1 = ''F''2 = 1이다. 그러면 ''F''43 = ''F''42 + ''F''41이고, ''F''42 = ''F''41 + ''F''40이다. 이제 ''F''41은 ''F''43과 ''F''42의 재귀적 하위 트리 모두에서 해결된다. 부분 문제의 총 개수가 실제로는 작음에도 불구하고(43개뿐), 이러한 단순한 재귀적 해법을 사용한다면 동일한 문제를 반복해서 해결하게 된다. 동적 계획법은 이러한 사실을 고려하여 각 부분 문제를 한 번만 해결한다.

이것은 두 가지 방법으로 달성할 수 있다.[4]

  • ''하향식 접근 방식'': 이것은 모든 문제의 재귀적 공식에서 직접적으로 파생된다. 임의의 문제에 대한 해를 하위 문제의 해를 사용하여 재귀적으로 공식화할 수 있고, 해당 하위 문제가 겹치는 경우, 부분 문제의 해를 메모이제이션하거나 저장할 수 있다. 새로운 부분 문제를 해결하려고 시도할 때마다, 먼저 표를 확인하여 이미 해결되었는지 확인한다. 해가 기록되어 있으면, 이를 직접 사용할 수 있으며, 그렇지 않은 경우 부분 문제를 해결하고 그 해를 표에 추가한다.
  • ''상향식 접근 방식'': 문제를 하위 문제 측면에서 재귀적으로 해결하는 방식을 공식화했다면, 상향식 방식으로 문제를 재구성해 볼 수 있다. 즉, 먼저 하위 문제를 해결하고 그 해를 사용하여 더 큰 하위 문제의 해를 구축하고 도출해 본다. 이는 또한 일반적으로 작은 하위 문제의 해를 사용하여 더 큰 하위 문제의 해를 반복적으로 생성하여 표 형식으로 수행된다. 예를 들어, 이미 ''F''41과 ''F''40의 값을 알고 있다면, ''F''42의 값을 직접 계산할 수 있다.


일부 프로그래밍 언어는 특정 인수 집합으로 함수 호출의 결과를 자동으로 메모이제이션하여 이름에 의한 호출 평가 속도를 높일 수 있다. 일부 언어는 이식 가능하게 만들 수 있다(예: Scheme, Common Lisp, Perl 또는 D). 일부 언어는 자동 메모이제이션이 내장되어 있다. 어떤 경우든, 이것은 참조 투명 함수에 대해서만 가능하며, 메모이제이션은 또한 울프럼 언어와 같은 용어 재작성 기반 언어 내에서 쉽게 접근할 수 있는 디자인 패턴으로 나타난다.

7. 2. 생물 정보학

생물정보학에서 서열 정렬, 단백질 접힘, RNA 구조 예측, 단백질-DNA 결합과 같은 작업에 동적 계획법이 널리 사용된다. 단백질-DNA 결합에 대한 최초의 동적 계획법 알고리즘은 1970년대에 미국에서 찰스 델리시에 의해[6], 소련에서 게오르기 구르스키와 알렉산더 자세데레프에 의해 독립적으로 개발되었다.[7] 최근 이러한 알고리즘은 생물정보학과 계산 생물학에서, 특히 뉴클레오솜 위치 및 전사 인자 결합 연구에서 매우 인기를 얻고 있다.

유전학에서, 서열 정렬은 동적 계획법이 필수적인 중요한 응용 분야이다.[17] 일반적으로 이 문제는 하나의 서열을 요소의 교체, 삽입 또는 제거와 같은 편집 연산을 사용하여 다른 서열로 변환하는 것으로 구성된다. 각 연산에는 연관된 비용이 있으며, 목표는 총 비용이 가장 낮은 일련의 편집을 찾는 것이다.

문제는 재귀로 표현될 수 있는데, 서열 A는 다음과 같은 방법으로 서열 B로 최적으로 편집된다.

# B의 첫 번째 문자를 삽입하고, A와 B의 꼬리에 대한 최적 정렬을 수행한다.

# A의 첫 번째 문자를 삭제하고, A의 꼬리와 B에 대한 최적 정렬을 수행한다.

# A의 첫 번째 문자를 B의 첫 번째 문자로 바꾸고, A와 B의 꼬리에 대한 최적 정렬을 수행한다.

부분 정렬은 행렬로 표로 나타낼 수 있으며, 여기서 셀 (i,j)는 A[1..i]에서 B[1..j]까지의 최적 정렬 비용을 포함한다. 셀 (i,j)의 비용은 관련 연산의 비용을 인접한 셀의 비용에 더하고 최적값을 선택하여 계산할 수 있다.

다양한 변형이 존재하며, 스미스-워터만 알고리즘과 니들만-분쉬 알고리즘을 참조하라.

7. 3. 제어 이론

제어 이론에서 일반적인 문제는 시스템 \dot{\mathbf{x}}(t) = \mathbf{g} \left( \mathbf{x}(t), \mathbf{u}(t), t \right)가 연속 시간 구간 t_{0} \leq t \leq t_{1}에서 허용 가능한 궤적 \mathbf{x}^{\ast}를 따르도록 하는 허용 가능한 제어 \mathbf{u}^{\ast}를 찾는 것이다. 이는 다음 손실 함수를 최소화한다.

:J = b \left( \mathbf{x}(t_{1}), t_{1} \right) + \int_{t_{0}}^{t_{1}} f \left( \mathbf{x}(t), \mathbf{u}(t), t \right) \mathrm{d} t

이 문제의 해결책은 최적 궤적 \mathbf{x}^{\ast}와 비용-대-가치 함수 J^{\ast}를 생성하는 최적 제어 법칙 또는 정책 \mathbf{u}^{\ast} = h(\mathbf{x}(t), t)이다. 후자는 동적 프로그래밍의 기본 방정식을 따른다.

:- J_{t}^{\ast} = \min_{\mathbf{u}} \left\{ f \left( \mathbf{x}(t), \mathbf{u}(t), t \right) + J_{x}^{\ast \mathsf{T}} \mathbf{g} \left( \mathbf{x}(t), \mathbf{u}(t), t \right) \right\}

여기서 J_{x}^{\ast} = \frac{\partial J^{\ast}}{\partial \mathbf{x}} = \left[ \frac{\partial J^{\ast}}{\partial x_{1}} ~~~~ \frac{\partial J^{\ast}}{\partial x_{2}} ~~~~ \dots ~~~~ \frac{\partial J^{\ast}}{\partial x_{n}} \right]^{\mathsf{T}}이고 J_{t}^{\ast} = \frac{\partial J^{\ast}}{\partial t}인 편미분 방정식이며, 이는 해밀턴-야코비-벨만 방정식으로 알려져 있다.[2] t, \mathbf{x} 및 알려지지 않은 함수 J_{x}^{\ast}의 관점에서 \mathbf{u}를 최소화한 다음 결과를 해밀턴-야코비-벨만 방정식에 대입하여 경계 조건 J \left( t_{1} \right) = b \left( \mathbf{x}(t_{1}), t_{1} \right)으로 풀 편미분 방정식을 얻는다. 실제로는, 이는 정확한 최적화 관계에 대한 몇 가지 이산 근사를 위해 일반적으로 수치적 편미분 방정식이 필요하다.

연속 프로세스를 이산 시스템으로 근사할 수 있으며, 이는 해밀턴-야코비-벨만 방정식과 유사한 다음 재귀 관계를 이끌어낸다.

:J_{k}^{\ast} \left( \mathbf{x}_{n-k} \right) = \min_{\mathbf{u}_{n-k}} \left\{ \hat{f} \left( \mathbf{x}_{n-k}, \mathbf{u}_{n-k} \right) + J_{k-1}^{\ast} \left( \hat{\mathbf{g}} \left( \mathbf{x}_{n-k}, \mathbf{u}_{n-k} \right) \right) \right\}

균등하게 간격을 둔 n개의 이산 시간 간격의 k번째 단계에서, 여기서 \hat{f}와 \hat{\mathbf{g}}는 f와 \mathbf{g}에 대한 이산 근사를 나타낸다. 이 함수 방정식은 벨만 방정식으로 알려져 있으며, 최적화 방정식의 이산 근사에 대한 정확한 해를 얻기 위해 풀 수 있다.[3]

7. 4. 경제학

경제학에서 동적 계획법은 사회 후생 함수를 최대화하는 데 사용된다. 람세이-캐스-쿠프만스 모형에서, 이는 현재 소비와 미래 소비 사이의 상충 관계, 즉 기간 간 선택 문제를 해결하는 데 적용된다. 미래 소비는 일정 할인율 \beta \in (0,1)로 할인된다. 자본의 이행 방정식에 대한 이산 근사는 다음과 같다.

:k_{t+1} = \hat{g} \left( k_{t}, c_{t} \right) = f(k_{t}) - c_{t}

여기서 c는 소비, k는 자본, f는 이나다 조건을 만족하는 생산 함수이다.

소비자는 매 기간마다 미래 효용을 요소 (0)로 할인하며, 기간 의 자본을 k_t라고 할 때, 초기 자본 k_0>0이 주어지고, 이번 기간의 자본과 소비가 다음 기간의 자본을 k_{t+1}=Ak^a_t - c_t로 결정한다. 소비자의 의사 결정 문제는 다음과 같이 표현할 수 있다.

:\max \sum_{t=0}^T b^t \ln(c_t) subject to k_{t+1}=Ak^a_t - c_t \geq 0 for all t=0,1,2,\ldots,T

이 문제는 모든 선택 변수 c_0, c_1, c_2, \ldots , c_T에 대해 풀이를 해야 하므로 복잡해 보이지만, 동적 프로그래밍 접근 방식을 통해 일련의 작은 결정으로 나눌 수 있다. 각 시간 에 자본 를 갖는 가치를 나타내는 가치 함수 V_t(k)를 정의하고, 역진 귀납법을 사용하여 벨만 방정식으로 계산할 수 있다. 벨만 방정식은 다음과 같다.

:V_t(k_t) \, = \, \max \left( \ln(c_t) + b V_{t+1}(k_{t+1}) \right) subject to k_{t+1}=Ak^a_t - c_t \geq 0

이를 통해 소비자는 전체 계획을 한 번에 선택하는 대신, 한 단계씩 문제를 해결할 수 있다.

역으로 작업하면, 시간 t=T-j의 가치 함수는 다음과 같다.

:V_{T-j}(k) \, = \, a \sum_{i=0}^j a^ib^i \ln k + v_{T-j}

시간 t=T-j에 소비하기에 최적의 양은 다음과 같다.

:c_{T-j}(k) \, = \, \frac{1}{\sum_{i=0}^j a^ib^i} Ak^a

이는 다음과 같이 단순화할 수 있다.

:\begin{align}

c_{T}(k) & = Ak^a\\

c_{T-1}(k) & = \frac{Ak^a}{1+ab}\\

c_{T-2}(k) & = \frac{Ak^a}{1+ab+a^2b^2}\\

&\dots\\

c_2(k) & = \frac{Ak^a}{1+ab+a^2b^2+\ldots+a^{T-2}b^{T-2}}\\

c_1(k) & = \frac{Ak^a}{1+ab+a^2b^2+\ldots+a^{T-2}b^{T-2}+a^{T-1}b^{T-1}}\\

c_0(k) & = \frac{Ak^a}{1+ab+a^2b^2+\ldots+a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^Tb^T}

\end{align}

결론적으로, 나이가 들어감에 따라 현재 자산의 더 큰 부분을 소비하는 것이 최적이며, 마지막 생애 기간인 에 나머지 자산 전체를 소비한다.

참조

[1] 서적 Introduction to Algorithms MIT Press & McGraw–Hill
[2] 서적 Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management https://books.google[...] Elsevier
[3] 서적 Optimal Control Theory: An Introduction https://books.google[...] Prentice-Hall
[4] 웹사이트 Algorithms by Jeff Erickson https://jeffe.cs.ill[...] 2024-12-06
[5] 웹사이트 M. Memo http://www.jsoftware[...] J Software 2011-10-28
[6] 간행물 Cooperative phenomena in homopolymers: An alternative formulation of the partition function 1974-07
[7] 간행물 Precise relationships for calculating the binding of regulatory proteins and other lattice ligands in double-stranded polynucleotides 1978-09
[8] 간행물 Dijkstra's algorithm revisited: the dynamic programming connexion http://matwbn.icm.ed[...]
[9] 간행물 Dynamic Programming: Models and Applications Dover Publications
[10] 간행물 Dynamic Programming: Foundations and Principles Taylor & Francis
[11] 논문 A note on two problems in connexion with graphs 1959-12
[12] 간행물 OR/MS Games: 2. The Towers of Hanoi Problem
[13] 서적 Which way did the Bicycle Go? https://books.google[...] The Mathematical Association of America
[14] 논문 OR/MS Games: 4. The Joy of Egg-Dropping in Braunschweig and Hong Kong
[15] 간행물 Connections between combinatorics of permutations and algorithms and geometry https://ir.library.o[...]
[16] 문서 Richard Bellman on the birth of Dynamical Programming https://web.archive.[...]
[17] 논문 What is Dynamic Programming?
[18] 서적 Numerical Optimization https://archive.org/[...] Springer
[19] 서적 Artificial Intelligence: A Modern Approach Prentice Hall
[20] 웹사이트 Richard E. Bellman Control Heritage Award http://a2c2.org/awar[...] 2004-07-01
[21] 문서 An introduction to the theory of dynamic programming The Rand Corporation
[22] 논문 The theory of dynamic programming http://www.rand.org/[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com